package Algorithm.backTracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 131. 分割回文串 https://leetcode.cn/problems/palindrome-partitioning
 * 题目简述：给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。
 */
public class Partition {

    /**
     * 思路：回溯算法。关键点在于每一步的选择列表为以begin开头切子串的方式，尾标i范围[begin,length-1]
     * 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：s中以下标begin开头的子串）
     * 回溯递归函数体：1.若begin==length，说明已切完，则path加入结果集然后return
     *              2.遍历当前选择列表：若选择切出的子串[begin,i]不是回文串则直接continue遍历同层其他选择，否则将子串加入路径，
     *                  然后递归下一步选择列表[i+1, length-1]，完毕后撤销上一步选择，继续遍历同层其他选择。
     */
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        Deque<String> path = new ArrayDeque<>();
        backTracking(result, path, s, 0);
        return result;
    }

    /**
     * 关键是能将问题求解过程抽象为树形结构
     */
    public void backTracking(List<List<String>> result, Deque<String> path, String s, int begin) {
        if(begin == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        //遍历路径选择列表：begin开头的剩余子串
        for(int i=begin;i < s.length();i++) {
            String subStr = s.substring(begin, i+1);
            //剪枝，若当前选择不是回文串则直接continue
            if(!isPalindrome(subStr))
                continue;
            path.add(subStr);
            backTracking(result, path, s, i+1);
            path.removeLast();
        }
    }

    /**
     * 判断一个字符串是否为回文串：i < len/2的部分与右边的部分比较
     */
    public boolean isPalindrome(String str) {
        int len = str.length();
        for(int i=0;i < len/2;i++) {
            if(str.charAt(i) != str.charAt(len-1-i)) {
                return false;
            }
        }
        return true;
    }
}
